Journals
  Publication Years
  Keywords
Search within results Open Search
Please wait a minute...
For Selected: Toggle Thumbnails
Maximal clique searching algorithm for hypergraphs
Lantian XU, Ronghua LI, Yongheng DAI, Guoren WANG
Journal of Computer Applications    2023, 43 (8): 2319-2324.   DOI: 10.11772/j.issn.1001-9081.2022091334
Abstract398)   HTML49)    PDF (1332KB)(306)       Save

Most of entity relationships in the real world cannot be represented by simple binary relations, and hypergraph can represent the n-ary relations among entities well. Therefore, definitions of hypergraph clique and maximal clique were proposed, and the exact algorithm and approximation algorithm for searching hypergraph maximal clique were given. First, the reason why the existing maximal clique searching algorithms on ordinary graphs cannot be applied to hypergraphs directly was analyzed. Then, based on the characteristics of hypergraph and the definition of maximal clique, a novel data structure for preserving the adjacency relations among hyperpoints was proposed, and an accurate maximal clique searching algorithm on hypergraph was proposed. As the running of the exact algorithm is slow, the pruning idea of pivots was combined with, the number of recursive layers was reduced, and an approximation maximal clique searching algorithm on hypergraph was proposed. Experimental results on multiple real hypergraph datasets show that under the premise finding most maximal cliques, the proposed approximation algorithm improves the search speed. When the number of test hypergraph cliques on 3-uniform hypergraph is 22, the acceleration ratio reaches over 1 000.

Table and Figures | Reference | Related Articles | Metrics